#include<stdio.h>
#include<malloc.h>

typedef struct V adj_tb;
typedef struct L link;
struct V{ int count; link* link; };
struct L{ int number;link* next; };

link* new_link(int number){
    link* l = malloc(sizeof(link));
    l->number = number;
    l->next = NULL;
    return l;
}

void adj_tb_add_link(adj_tb* tb,link* l){
    int i; link* cur = tb->link;
    if(cur==NULL){tb->link = l;tb->count=1;return; }
    for(i=1;i<tb->count;i++)cur = cur->next;
    cur->next = l; tb->count++;
}

void adj_tb_del(adj_tb* tb,int n){
    int i,j; link* cur,*tmp;
    for(i=0;i<n;i++){
        cur = tb[i].link;
        for(j=0;j<tb[j].count;j++){
            tmp = cur->next;free(cur);cur=tmp;
        }
    }
    free(tb);
}

void print_adj_tb(const adj_tb* tb,int n){
    int i,j; link* cur;
    printf("<Adjacency Table with %d vert%s>\n",n,n>1?"ices":"ex");
    for(i=0;i<n;i++){
        printf("%4d|",i+1); cur = tb[i].link;
        for(j=0;j<tb[i].count;j++){printf("%d ",cur->number);cur = cur->next;}
        putchar('\n');
    }
}

void adj_tb_dfs_non_recursive(const adj_tb* tb,int n,int from,int to){
    int i,ip,cur; link* l;
    int* vis = malloc(sizeof(int)*n);
    int* stack = malloc(sizeof(int)*n);
    int* exh = malloc(sizeof(int)*n);
    for(i=0;i<n;i++)vis[i]=exh[i]=0;
    ip = 0; stack[ip++] = from;
    vis[from] = 1;
    while( stack[ip-1] != to && ip ){
        cur = stack[ip-1];
        if(vis[cur]==-1){
            // printf("vis[%d]=%d Pop %d\n",cur,vis[cur],stack[ip-1]);
            vis[stack[--ip]]=0;continue;
        }
        if(exh[cur]==tb[cur].count){
            // printf("exh[%d]=%d tb[%d].count=%d Pop %d\n",cur,exh[cur],cur,tb[cur].count,stack[ip-1]);
            vis[cur]=-1;vis[stack[--ip]]=-1;continue;
        }
        l = tb[cur].link;
        for(i=0;i<exh[cur];i++)l=l->next; exh[cur]++;
        if(vis[l->number-1]==0){
            stack[ip++] = l->number-1;  vis[stack[ip-1]]=1;
            // printf("Push %d exh[%d]=%d\n",stack[ip-1],cur,exh[cur]);
        }
    }
    if(ip==0)printf("No Path.");
    else for(i=0;i<ip;i++)printf("%d ",stack[i]+1);
    putchar('\n');
    free(vis); free(stack); free(exh);
}

int main(){
    int n,i,j,buf;
    printf("Enter verteice count: ");
    scanf("%d",&n);
    printf("Enter adjacent vertices for each vertex, end with -1:\n");
    adj_tb* tb = malloc(sizeof(adj_tb)*n);
    for(i =0;i<n;i++){
        tb[i].count = 0; tb[i].link = NULL;
        printf("v[%d]> ",i+1);
        for(j=0;j<n;j++){
            scanf("%d",&buf);
            if(buf==-1)break;
            adj_tb_add_link(tb+i,new_link(buf));
        }
    }
    printf("Get Adjacency Table:\n");print_adj_tb(tb,n);
    printf("Enter Path start and finish vertex: ");
    scanf("%d%d",&i,&j);
    printf("Find Path: %d -> %d\n",i,j);
    adj_tb_dfs_non_recursive(tb,n,i-1,j-1);
    adj_tb_del(tb,n);
    return 0;
}